{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 批处理问题 \n",
    "LeetCode 原题链接:\n",
    "[LeetCode 32](https://leetcode-cn.com/problems/t3fKg1/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## LCP 32. 批量处理任务\n",
    "某实验室计算机待处理任务以 [start,end,period] 格式记于二维数组 tasks，表示完成该任务的时间范围为起始时间 start 至结束时间 end 之间，需要计算机投入 period 的时长，注意：\n",
    "\n",
    "period 可为不连续时间\n",
    "首尾时间均包含在内\n",
    "处于开机状态的计算机可同时处理任意多个任务，请返回电脑最少开机多久，可处理完所有任务。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 题解:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def processTasks(self, tasks) -> int:\n",
    "        tasks.append([10**9+1, 10**9+1, 1]) #加个哨兵\n",
    "        res, q = 0, []\n",
    "        for [s, e, p] in sorted(tasks, key=lambda x:x[0]) :\n",
    "            while q and q[0][0]+res < s :\n",
    "                if q[0][0]+res >= q[0][1]: heapq.heappop(q) #任务早已完成，移除\n",
    "                else : res += min(q[0][1], s) - (q[0][0]+res)\n",
    "            heapq.heappush(q, [e-p+1-res, e+1])\n",
    "        return res"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
